Grokking Meta Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Meta Easy Problems
Toeplitz Matrix (easy)
Solution: Toeplitz Matrix
Remove All Adjacent Duplicates In String (easy)
Solution: Remove All Adjacent Duplicates In String
Minimum Depth of a Binary Tree (easy)
Solution: Minimum Depth of a Binary Tree
Tree Diameter (easy)
Solution: Tree Diameter
Island Perimeter (easy)
Solution: Island Perimeter
Moving Average from Data Stream (easy)
Solution: Moving Average from Data Stream
Move Zeroes (easy)
Solution: Move Zeroes
Missing Ranges (easy)
Solution: Missing Ranges
Palindrome Permutation (easy)
Solution: Palindrome Permutation
Rank Transform of an Array (easy)
Solution: Rank Transform of an Array
Meta Medium Problems
Diagonal Traverse (medium)
Solution: Diagonal Traverse
Shortest Path in Binary Matrix (medium)
Solution: Shortest Path in Binary Matrix
Maximum Swap (medium)
Solution: Maximum Swap
Custom Sort String (medium)
Solution: Custom Sort String
Binary Tree Vertical Order Traversal (medium)
Solution: Binary Tree Vertical Order Traversal
Buildings With an Ocean View (medium)
Solution: Buildings With an Ocean View
Basic Calculator II (medium)
Solution: Basic Calculator II
Nested List Weight Sum (medium)
Solution: Nested List Weight Sum
Dot Product of Two Sparse Vectors (medium)
Solution: Dot Product of Two Sparse Vectors
Max Consecutive Ones III (medium)
Solution: Max Consecutive Ones III
Subarray Sum Equals K (medium)
Solution: Subarray Sum Equals K
Next Permutation (medium)
Solution: Next Permutation
Simplify Path (medium)
Solution: Simplify Path
Lowest Common Ancestor of a Binary Search Tree (medium)
Solution: Lowest Common Ancestor of a Binary Search Tree
'K' Closest Points to the Origin (medium)
Solution: 'K' Closest Points to the Origin
Sum of Path Numbers (medium)
Solution: Sum of Path Numbers
Merge Intervals (medium)
Solution: Merge Intervals
Right View of a Binary Tree (medium)
Solution: Right View of a Binary Tree
Number of Islands (medium)
Solution: Number of Islands
Clone Graph (medium)
Solution: Clone Graph
Missing Element in Sorted Array (medium)
Solution: Missing Element in Sorted Array
Number of Substrings Containing All Three Characters (medium)
Solution: Number of Substrings Containing All Three Characters
Capacity To Ship Packages Within D Days (medium)
Solution: Capacity To Ship Packages Within D Days
Count and Say (medium)
Solution: Count and Say
Contiguous Array (medium)
Solution: Contiguous Array
Sliding Window Median (hard)
Solution: Sliding Window Median
Alien Dictionary (hard)
Solution: Alien Dictionary
Minimum Window Substring (hard)
Solution: Minimum Window Substring
Best Meeting Point (hard)
Solution: Best Meeting Point
Maximum Sum of 3 Non-Overlapping Subarrays (hard)
Solution: Maximum Sum of 3 Non-Overlapping Subarrays
Making A Large Island (hard)
Solution: Making A Large Island
Basic Calculator (Hard)
Solution: Basic Calculator
Serialize and Deserialize Binary Tree (hard)
Solution: Serialize and Deserialize Binary Tree
Longest Increasing Path in a Matrix (hard)
Solution: Longest Increasing Path in a Matrix
Valid Palindrome III (hard)
Solution: Valid Palindrome III
Solution: Contiguous Array

Problem Statement

Given an array nums containing only 1 and 0 digits, return the maximum length of the contiguous subarray having an equal number of 1 and 0.

Examples

  • Example 1:
    • Input: [0, 1]
    • Expected Output: 2
    • Justification: The longest subarray with equal numbers of 0s and 1s is [0, 1].
  • Example 2:
    • Input: [1, 1, 0, 0, 1, 1, 0]
    • Expected Output: 6
    • Justification: The subarray [1, 0, 0, 1, 1, 0] contains three 0s and three 1s.
  • Example 3:
    • Input: [0, 1, 1, 0, 1, 0, 0, 1, 1]
    • Expected Output: 8
    • Justification: The subarray from the first to the eighth element is the longest with an equal number of 0s and 1s.

Solution

To solve this problem, we'll utilize a hash map to keep track of the balance between 0s and 1s at each index. The balance is calculated by treating 0 as -1 and 1 as +1 and adding these values cumulatively. The hash map will store each unique cumulative balance with its earliest index. If we encounter the same balance again, it means the subarray between these two indices has an equal number of 0s and 1s. The reason this approach is effective is that it reduces the problem to a single pass through the array, updating the hash map and checking for the longest balanced subarray as we go.

Step-by-step Algorithm

  1. Initialize Variables:

    • Create a map/dictionary balanceMap to keep track of cumulative balances and their first occurrence indexes.
    • Initialize two variables: cumulativeBalance to 0 (to keep track of the balance between 0s and 1s) and maxLength to 0 (to store the length of the longest subarray found).
  2. Iterate Through the Array:

    • Loop through each element of the array, using a variable i for indexing.
  3. Update Cumulative Balance:

    • For each element, update cumulativeBalance. Decrease by 1 if the element is 0; otherwise, increase by 1.
  4. Check and Update the Map:

    • If cumulativeBalance is already present in balanceMap, calculate the length of the current balanced subarray by subtracting the index stored in balanceMap[cumulativeBalance] from the current index i. Update maxLength if this length is greater than the current maxLength.
    • If cumulativeBalance is not present in balanceMap, add it to the map with the value of the current index i.
  5. Return the Result:

    • After the loop, return maxLength as the result.

Algorithm Walkthrough

Using Example 2: [1, 1, 0, 0, 1, 1, 0]

  1. Initialization:

    • balanceMap = {0: -1}
    • cumulativeBalance = 0, maxLength = 0
  2. Iterate and Update:

    • Index 0 (Element 1):

      • Update cumulativeBalance to 1.
      • Update balanceMap: {0: -1, 1: 0}
      • maxLength: 0 (no change).
    • Index 1 (Element 1):

      • Update cumulativeBalance to 2.
      • Update balanceMap: {0: -1, 1: 0, 2: 1}
      • maxLength: 0 (no change).
    • Index 2 (Element 0):

      • Update cumulativeBalance to 1 (since it's seen before, check for subarray).
      • balanceMap: {0: -1, 1: 0, 2: 1}
      • maxLength: max(0, 2 - 0) = 2 (subarray from index 0 to 2).
    • Index 3 (Element 0):

      • Update cumulativeBalance to 0 (seen before, check for subarray).
      • balanceMap: {0: -1, 1: 2, 2: 1}
      • maxLength: max(2, 3 - (-1)) = 4 (subarray from index 0 to 3).
    • Index 4 (Element 1):

      • Update cumulativeBalance to 1 (seen before, check for subarray).
      • balanceMap: {0: -1, 1: 0, 2: 1}
      • maxLength: max(4, 4 - 0) = 4 (no change).
    • Index 5 (Element 1):

      • Update cumulativeBalance to 2 (seen before, check for subarray).
      • balanceMap: {0: -1, 1: 0, 2: 1}
      • maxLength: max(4, 5 - 1) = 4 (no change).
    • Index 6 (Element 0):

      • Update cumulativeBalance to 1 (seen before, check for subarray).
      • balanceMap: {0: -1, 1: 0, 2: 1}
      • maxLength: max(4, 6 - 0) = 6 (subarray from index 0 to 6).
  3. Result:

    • Final maxLength is 6, which is the length of the longest contiguous subarray with an equal number of 0s and 1s.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

The algorithm traverses the array once so time complexity is O(n), where n is the length of the array. Map/dictionary operations like insertion and lookup take O(1) time on average, so the time complexity is linear.

Space Complexity

In the worst case, the map/dictionary might store an entry for every element in the array, leading to a space complexity proportional to the size of the input array, i.e., O(n) .

Contiguous Array (medium)
Sliding Window Median (hard)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity